Cache Simulations

April 19, 2012

Prelab (complete before lab)

In this lab you will use the C programming language to write simulators for several cache architectures and evaluate their performance on a specific code fragment. The miniMIPS code fragment that will be used is shown below.

main:   addu    $t0,$0,$0
        addiu   $t1,$0,80
        addu    $t2,$0,$0
loop:   lw      $t3,array($t0)
        addu    $t2,$t2,$t3
        addiu   $t0,$t0,4
        bne     $t0,$t1,loop
*done:  beq     $0,$0,done

array:  .word   1,2,3,4,5,6,7,8,9,10
        .word   11,12,13,14,15,16,17,18,19,20

Prior to lab, do the following. Load the given code fragment into the miniMIPs simulator, assemble it, and execute it. When the breakpoint is reached press the [Output Trace] button. This should pop up a dialog with a the series of memory adddresses accessed by the program. Copy and Paste this list of addresses into an editor running on the UNIX host (pico, vim, emacs, etc.) and save it as the file "trace.txt". Your trace file should have 103 lines.

Part 1: A direct-mapped cache

The following code fragment simulates a direct-mapped cache with 8 lines of 1 word.

#include <stdio.h>

int tag[8];

int main( )
{
    int addr;
    int i, j, t;
    int hits, accesses;
    FILE *fp;

    fp = fopen("trace.txt", "r");
    hits = 0;
    accesses = 0;
    while (fscanf(fp, "%x", &addr) > 0) {
        /* simulate a direct-mapped cache with 8 words */
        accesses += 1;
        printf("%3d: 0x%08x ", accesses, addr);
        i = (addr >> 2) & 7;
        t = addr | 0x1f;
        if (tag[i] == t) {
            hits += 1;
            printf("Hit%d ", i);
        } else {
            /* allocate entry */
            printf("Miss ");
            tag[i] = t;
        }
        for (i = 0; i < 8; i++)
            printf("0x%08x ", tag[i]);
        printf("\n");
    }
    printf("Hits = %d, Accesses = %d, Hit ratio = %f\n", hits, accesses, ((float)hits)/accesses);
    close(fp);
}

The structure of the code is as follows. First, the trace file is opened and each address is read from it (i.e. the fscanf() function call) into the variable addr. The index and tag parts of the address are extracted into the variables i and t respectively. The part of the address associated with the tag, t, is then compared to the tag at the specified index. If they match, a hit is recorded. On a miss the tag is updated to reflect the replaced cache entry. This cache simulator outputs a line for every meomory access. When the end of the trace file is reached a summary is printed out.

Checkoff #1: Compile and execute the direct-mapped cache simulator given above. Report the final number of hits and accesses output by the code. Also, based on the pattern of cache hits, estimate the hit rate of the given miniMIPs code fragment in the steady state (once the compulsary misses are accounted for).

Part 2: A fully-associative cache

The next program simulates a fully associative cache with 8 lines each of 1 word.

include <stdio.h>

int tag[8];
int mru[8] = {7,6,5,4,3,2,1,0};

void mruUpdate(int index)
{
    int i;
    // find index in mru
    for (i = 0; i < 8; i++)
        if (mru[i] == index)
            break;
    // move earlier refs one later
    while (i > 0) {
        mru[i] = mru[i-1];
        i--;
    }
    mru[0] = index;
}

int main( )
{
    int addr;
    int i, j, t;
    int hits, accesses;
    FILE *fp;
    
    fp = fopen("trace.txt", "r");
    hits = 0;
    accesses = 0;
    while (fscanf(fp, "%x", &addr) > 0) {
        /* simulate fully associative cache with 8 words */
        accesses += 1;
        printf("%3d: 0x%08x ", accesses, addr);
        for (i = 0; i < 8; i++) {
            if (tag[i] == addr) {
                hits += 1;
                printf("Hit%d ", i);
                mruUpdate(i);
                break;
            }
        }
        if (i == 8) {
            /* allocate entry */
            printf("Miss ");
            i = mru[7];
            tag[i] = addr;
            mruUpdate(i);
        }
        for (i = 0; i < 8; i++)
            printf("0x%08x ", tag[i]);
        for (i = 0; i < 8; i++)
            printf("%d ", mru[i]);
        printf("\n");
    }
    printf("Hits = %d, Accesses = %d, Hit ratio = %f\n", hits, accesses, ((float)hits)/accesses);
    close(fp);
}

This program maintains an array with 8 tags and the most-recently-used ordering of the lines in the array mru[]. When each address is read from the trace file, it is compared to all of the tags in the cache in the first for loop. If the tag is found, a hit is recorded, and the mru[] array is updated using the mruUpdate() function, and the loop is exited via the break statement. A miss is detected when no matches are found after searching all 8 tags. In this case the loop index, i, will be set to 8. On a miss the least recently-used tag, which should be the last element in mru[], is chosen for replacement, the tag is updated, and the mru[] array is updated.

As before, the cache simulator outputs a line for every meomory access. When the end of the trace file is reached a summary is printed out.

Checkoff #2: Compile and execute the fully-associative cache simulator provided above. Report the final number of hits and accesses output by the code. Based on the pattern of cache hits, estimate the hit rate of the given miniMIPs code fragment in the steady state (once the compulsary misses are accounted for).